package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;
import java.util.Random;
import java.io.EOFException;


/**
 * A <tt>UserProcess</tt> that supports demand-paging.
 */
public class VMProcess extends UserProcess {
    /**
     * Allocate a new process.
     */
    public VMProcess() {
	super();
    }

    /**
     * Save the state of this process in preparation for a context switch.
     * Called by <tt>UThread.saveState()</tt>.
     */
    public void saveState() {	
	    super.saveState();
      //System.out.println("Context Switch!");
	    // set all entries to invalid
	    for(int i = 0; i<Machine.processor().getTLBSize(); i++){
		    TranslationEntry t =  Machine.processor().readTLBEntry(i);
        t.valid = false;
        Machine.processor().writeTLBEntry(i, t);
	    }	
    }

    /**
     * Restore the state of this process after a context switch. Called by
     * <tt>UThread.restoreState()</tt>.
     */
    public void restoreState() {
	//super.restoreState();
    }

    /**
     * Initializes page tables for this process so that the executable can be
     * demand-paged.
     *
     * @return	<tt>true</tt> if successful.
     */
    protected boolean loadSections() {
	    //pageTable2 = new NewTranslation[numPages];
	    //return super.loadSections();
      return true;
    }

    /**
     * Release any resources allocated by <tt>loadSections()</tt>.
     */
    protected void unloadSections() {

	IPTLock.acquire();
	for(int i=0;i<pageTable2.length;i++){
	   if(pageTable2[i].swap != -1){
   	       VMKernel.diskPagesAvailable.add(new Integer(pageTable2[i].swap));
           }
	   if(VMKernel.ipt[pageTable[i].ppn].pinned){
		VMKernel.ipt[pageTable[i].ppn].pinned = false;
	        VMKernel.numberOfPinned--;
                pinnedLock.acquire();
                allPinned.wake();
                pinnedLock.release();
	   }
	}

	super.unloadSections();


	IPTLock.release();			
    }
    

    protected void checkAddr(int vpn, boolean write){
	clockLock.acquire();
	  //if(write)
		//System.out.println("WRITE IS TRUE");
      //boolean inTLB = false;
      TranslationEntry t = new TranslationEntry();
      int tlbLoc = -1;

      TranslationEntry ent;// = pageTable[vpn];
      NewTranslation ent2;// = pageTable2[vpn]; 

      for(int i = 0; i < Machine.processor().getTLBSize(); ++i){
        tlbLoc = i;
        t = Machine.processor().readTLBEntry(i);
        if(t.valid){
	
	  ent = pageTable[t.vpn];

	  /* UPDATE PAGE TABLE WITH TLB */
          //System.out.println("VPN " + vpn + " is in the TLB");
          //inTLB = true;
          if(ent.ppn != t.ppn || ent.used != t.used || ent.dirty != t.dirty ||
             ent.valid != t.valid){
		//System.out.println("TLB is different from pageTable for vpn"+vpn);
		pageTable[t.vpn] = Machine.processor().readTLBEntry(tlbLoc);
	  }
            //Machine.processor().writeTLBEntry(tlbLoc, ent);
          

        }
      }
 
     ent = pageTable[vpn];
     ent2 = pageTable2[vpn]; 

     /* if(inTLB){
          if(ent.ppn != t.ppn || ent.used != t.used || ent.dirty != t.dirty ||
             ent.valid != t.valid){
		//System.out.println("TLB is different from pageTable for vpn"+vpn);
		pageTable[vpn] = Machine.processor().readTLBEntry(tlbLoc);

            //Machine.processor().writeTLBEntry(tlbLoc, ent);
          }
        }*/


      //Check to see if the entry got loaded into memory
      if(ent.valid == true){
	  //System.out.println("Entry is valid");
        //If the page was never messed with then just return it
        if(ent2.swap == -1){
	  //System.out.println("swap is -1 for vpn"+vpn+", ppn"+ent.ppn);
	  clockLock.release();
	  syncPageTabletoTLB();
          return; 
        }
        else{
          int ppage = -1;
          //Check for available pages
          if(VMKernel.pagesAvailable.size() != 0){
            ppage = VMKernel.pagesAvailable.remove();
          }
          //No available pages so steal one
          else{
            ppage = getClockPPN();
          }
			//System.out.println(PID +" 0");
          //Check if the old page was coff
			if(ent.readOnly && ent2.type == "coff"){
			  CoffSection oldcoff = coff.getSection(ent2.cSection);
				oldcoff.loadPage(ent2.pnum, ppage);
				//System.out.println("1");
			}          
			else{
				//System.out.println("GETTING stuff from disk");
				byte [] data = loadFromDisk(ent2.swap);
				VMKernel.diskPagesAvailable.add(new Integer(ent2.swap));
				//System.out.println("adding to diskPagesAvail "+ent2.swap);
				storeIntoPMem(data,ppage);
				//System.out.println("2");			      
			}
          //Update pagetables, global entry, and tlb with new data
          if(write){
            ent.dirty = true;
			//System.out.println("3");
          }
          ent.ppn = ppage;
          ent.used = true;
          ent2.swap = -1;
          GlobalEntry newg = new GlobalEntry(ppage, vpn, false, this);
          VMKernel.ipt[ppage] = newg;
          //Machine.processor().writeTLBEntry(i, ent);	
	  clockLock.release();	
	  syncPageTabletoTLB();  
          return;
        }
      }
      //Page entry never got loaded into memory so it's just a new page
      else{
        int ppage = -1;
        //Check for available pages
        if(VMKernel.pagesAvailable.size() != 0){
          ppage = VMKernel.pagesAvailable.remove();
        }
        //No available pages so steal one
        else{
          ppage = getClockPPN();		  
		  //System.out.println(PID +" 6");
        }

        //Find out what needs to be entered into memory
        if(ent2.type == "stack"){
          byte [] data = new byte[pageSize];
			    for(int j=0; j<data.length; j++){
				    data[j]=0x00;
          }
          ////System.out.println("Stack ppn given: " + ppage);
			    storeIntoPMem(data,ppage);
				//System.out.println(PID +" 7");
        }
        else if(ent2.type == "coff"){
            CoffSection oldcoff = coff.getSection(ent2.cSection);
			//if(PID == 2 && vpn == 9){
			 //System.out.println("pnum: "+ent2.pnum);
			 //System.out.println("isReadonly? "+ent.readOnly);
			//}
			oldcoff.loadPage(ent2.pnum, ppage);
			printOutMem(ppage);
				  
			//System.out.println(PID +" 8");				  
        }
        //Data is args, so load them into mem
        else{
          byte[][] argv = new byte[args.length][];
	        int argsSize = 0;
	        for (int j=0; j<args.length; j++) {
	          argv[j] = args[j].getBytes();
	          // 4 bytes for argv[] pointer; then string plus one for null byte
	          argsSize += 4 + argv[j].length + 1;
			  //System.out.println("9");
	        }

          int entryOffset = vpn*pageSize;
	        int stringOffset = entryOffset + args.length*4;
	        ent.ppn = ppage;
	        byte[] memory = Machine.processor().getMemory();

	        for (int j=0; j<argv.length; j++) {
	          byte[] stringOffsetBytes = Lib.bytesFromInt(stringOffset);				

	          System.arraycopy(stringOffsetBytes, 0, memory, entryOffset, stringOffsetBytes.length);
//	          Lib.assertTrue(writeVirtualMemory(entryOffset,stringOffsetBytes) == 4);

	          entryOffset += 4;

		  System.arraycopy(argv[j], 0, memory, stringOffset, argv[j].length);
	          //Lib.assertTrue(writeVirtualMemory(stringOffset, argv[j]) ==
		                                      //argv[j].length);
	          stringOffset += argv[j].length;

		  System.arraycopy(new byte[] { 0 }, 0, memory, stringOffset, 1);
//	          Lib.assertTrue(writeVirtualMemory(stringOffset,new byte[] { 0 }) == 1);
	          stringOffset += 1;
			  //System.out.println("10");
	        }
        }
        //Update pagetables, global entry, and tlb with new data
        ////System.out.println("Ent vpn: " + ent.vpn);
        if(write){
          //System.out.println("Should never reach here");
          ent.dirty = true;
        }
        ent.valid = true;
        ent.used = true;
        ent.dirty = false;
        ent.ppn = ppage;
        GlobalEntry newg = new GlobalEntry(ppage, vpn, false, this);
        VMKernel.ipt[ppage] = newg;

        //Machine.processor().writeTLBEntry(i, ent);
        ////System.out.println("hello");	
		printOutMem(ppage);
		//System.out.println(PID +" 100");		
		//unpinPhysicalPage(ppage);
	clockLock.release();
        syncPageTabletoTLB();

        return;
      }
    }

    protected void pinPage(int vaddr){
	    IPTLock.acquire();
	    int ppn = getPPN(vaddr);
	    VMKernel.ipt[ppn].pinned = true;
	    VMKernel.numberOfPinned++;
	    IPTLock.release();
    }
	
	protected void pinPhysicalPage(int ppn){
	    
	    VMKernel.ipt[ppn].pinned = true;
	    VMKernel.numberOfPinned++;
	    
    }

    protected void unpinPage(int vaddr){
	    
	    int ppn = getPPN(vaddr);
	    VMKernel.ipt[ppn].pinned = false;
	    VMKernel.numberOfPinned--;
	    pinnedLock.acquire();
        allPinned.wake();
        pinnedLock.release();
	    
    }
	
	protected void unpinPhysicalPage(int ppn){
	    IPTLock.acquire();
	    VMKernel.ipt[ppn].pinned = false;
	    VMKernel.numberOfPinned--;
	    pinnedLock.acquire();
        allPinned.wake();
        pinnedLock.release();
	    IPTLock.release();
    }

    private int getPPN(int vaddr){
       int vpn = vaddr / pageSize;
       int offset = vaddr % pageSize;
       TranslationEntry entry = pageTable[vpn];
       return entry.ppn;
    }

    protected void getIPTLock(){
	    this.IPTLock = new Lock();
	    this.pinnedLock = new Lock();
		this.TLBLock = new Lock();
		this.clockLock = new Lock();
		this.memLock = new Lock();
	    this.allPinned = new Condition(pinnedLock);
    }

    protected void passIPTLock(UserProcess process){
	    VMProcess process2 = (VMProcess) process;
	    process2.IPTLock = this.IPTLock;
      process2.pinnedLock = this.pinnedLock;
	  process2.TLBLock = this.TLBLock;
	  process2.clockLock = this.clockLock;
	  process2.memLock = this.memLock;
	    process2.allPinned = this.allPinned;
    }

    protected boolean load(String name, String[] args) {
 	    OpenFile executable = ThreadedKernel.fileSystem.open(name, false);
	    if (executable == null) {
	      Lib.debug(dbgProcess, "\topen failed");
	      return false;
	    }

	    try {
	      coff = new Coff(executable);
	    }
	    catch (EOFException e) {
	      executable.close();
	      Lib.debug(dbgProcess, "\tcoff load failed");
	      return false;
	    }
      
      //save args
      this.args = args;

	    // make sure the sections are contiguous and start at page 0
	    numPages = 0;
	    for (int s=0; s<coff.getNumSections(); s++) {
	      CoffSection section = coff.getSection(s);
	      if (section.getFirstVPN() != numPages) {
		      coff.close();
		      Lib.debug(dbgProcess, "\tfragmented executable");
		      return false;
	      }
	      numPages += section.getLength();
	    }

	    // make sure the argv array will fit in one page
	    byte[][] argv = new byte[args.length][];
	    int argsSize = 0;
	    for (int i=0; i<args.length; i++) {
	      argv[i] = args[i].getBytes();
	      // 4 bytes for argv[] pointer; then string plus one for null byte
	      argsSize += 4 + argv[i].length + 1;
	    }
	    if (argsSize > pageSize) {
	      coff.close();
	      Lib.debug(dbgProcess, "\targuments too long");
	      return false;
	    }

	    // program counter initially points at the program entry point
	    initialPC = coff.getEntryPoint();	

	    // next comes the stack; stack pointer initially points to top of it
	    numPages += stackPages;
      int stackvpn = numPages - 1;
	    initialSP = numPages*pageSize;

	    // and finally reserve 1 page for arguments
	    numPages++;
      
      int entryOffset = (numPages-1)*pageSize;
	    int stringOffset = entryOffset + args.length*4;

	    this.argc = args.length;
	    this.argv = entryOffset;
      
      //System.out.println("Number of pages requested: " + numPages);
      //Instantiate page tables
      pageTable = new TranslationEntry[numPages];
      pageTable2 = new NewTranslation[numPages];
      for (int i=0; i<numPages; i++){
	      pageTable[i] = new TranslationEntry(i,-1,false,false,false,false);
        pageTable2[i] = new NewTranslation();
      }

      //Instantiate coff sections in page tables
      for (int s=0; s<coff.getNumSections(); s++) {
	      CoffSection section = coff.getSection(s);
	    
	      Lib.debug(dbgProcess, "\tinitializing " + section.getName()
		              + " section (" + section.getLength() + " pages)");

	      for (int i=0; i<section.getLength(); i++) {
	        int vpn = section.getFirstVPN()+i;

	        //insert coff section info in page table
          //System.out.println("Instantiated coff pageTable2[" + vpn + "]");
          pageTable2[vpn].type = "coff";
          pageTable2[vpn].pnum = i;
	  //if(PID == 2 && vpn == 9)
		  //System.out.println("pageTable[9].pnum = "+i);
          pageTable2[vpn].swap = -1;
          pageTable2[vpn].cSection = s;

          if(section.isReadOnly()){
		//if(PID == 2 && vpn == 9)
			//System.out.println("setting READONLY to true");

		pageTable[vpn].readOnly = true;
          }
	      }
      }

      //Instantiate stack pages in page tables
      int j = 0;
      for(int i = stackvpn; i > stackvpn - stackPages; --i){
        //System.out.println("Instantiated stack pageTable2[" + i + "]");
        pageTable2[i].type = "stack";
        pageTable2[i].pnum = j;
        pageTable2[i].swap = -1;
        pageTable2[i].cSection = -1;
        ++j;
      }

      //Instantiate args in page tables
        int argvpn = numPages - 1;
        //System.out.println("Instantiated args pageTable2[" + argvpn + "]");
        pageTable2[argvpn].type = "args";
        pageTable2[argvpn].pnum = 0;
        pageTable2[argvpn].swap = -1;
        pageTable2[argvpn].cSection = -1;

      return true; 
    }

    private void handleTLBMiss(){
      //Need to implement universal lock just in case there's a context switch
      TLBLock.acquire();

      int badVA = Machine.processor().readRegister(Processor.regBadVAddr);
      int vpn = badVA/pageSize;
      int i = 0;
      boolean full = false;
      //System.out.println(PID+" Userspace access to vpn: " + vpn);

      //Random TLB replacement algorithm
      while(Machine.processor().readTLBEntry(i%Machine.processor().getTLBSize()).valid){
	      if(++i%Machine.processor().getTLBSize() == 0){			
		  full = true;
		  break;
  	      }
      }	
      if(full){ // steal!
	      Random r = new Random();
 	      i = r.nextInt(Machine.processor().getTLBSize());
      }
      
      TranslationEntry ent = pageTable[vpn];
      NewTranslation ent2 = pageTable2[vpn];
      //System.out.println("Inserting into TLB at position "+i);
      ////System.out.println("Loading: " + ent2.type + " " + ent2.pnum);
	  //System.out.println("1st:"+ent.ppn);
      checkAddr(vpn, false); 
	  //System.out.println("2nd:"+ent.ppn);
      Machine.processor().writeTLBEntry(i, ent);
	  //System.out.println("3rd:"+ent.ppn);
	  
	  printOutMem(ent.ppn);
	  TLBLock.release();
      return;

		  //TranslationEntry t = pageTable[vpn];
		  //if(t.valid == false)
		  //t.ppn = getPPN(badVA);
		  //t.valid = true;
		  //Machine.processor().writeTLBEntry(i,t);
      
    }


    /* Inverted Page Table 
     * Implements Clock Algorithm
     */
    public int getClockPPN(){
      
	IPTLock.acquire();  
      if(VMKernel.numberOfPinned == Machine.processor().getNumPhysPages()){ // all pinned
			//System.out.println("SLEEPING ON ALL PINNED");
			pinnedLock.acquire();
		    allPinned.sleep();
			pinnedLock.release();
      }
	  //IPTLock.acquire();

	updateIPT();

      while(true){
        GlobalEntry[] kipt = VMKernel.ipt;
      
	      for(int i = 0; i< kipt.length; i++){
                GlobalEntry g = kipt[i];
	        TranslationEntry te = g.vp.pageTable[g.vpn];
                NewTranslation te2 = g.vp.pageTable2[g.vpn];

	        if(te.used == false && g.pinned == false){ // store in swap file
            int swapLoc = -1;
            if(!te.readOnly && (te.dirty || te2.type == "coff")){
              swapLoc = evict(i);
            }
            else if(te.readOnly){
              //System.out.println("ReadOnly");
              te.valid = false;
            }
            te2.swap = swapLoc;
            
            for(int j = 0; j < Machine.processor().getTLBSize(); ++j){
              TranslationEntry t = Machine.processor().readTLBEntry(j);
              if(t.ppn == i){
                //System.out.println("Invalidated TLB entry: " + j);
                t.valid = false;
                Machine.processor().writeTLBEntry(j, t);
                break;
              }
            }
            //System.out.println("Physical page stolen"+i+" and vpn: " + te.vpn + " PID: " + 
//              PID);
			  //pinPhysicalPage(i);
			  IPTLock.release();			  		 
			  
            return i;
			    }
	    	  else{
		        te.used = false;
          }
        }
	    }
    }

    private void updateIPT(){
       
          GlobalEntry[] kipt = VMKernel.ipt;
      	   
	  for(int i = 0; i < Machine.processor().getTLBSize(); ++i){
             TranslationEntry t = Machine.processor().readTLBEntry(i);
             if(t.valid && t.used){
                kipt[t.ppn].vp.pageTable[t.vpn].used = t.used;	 
             }
          }
    }

    //Evict a page -- should be protected by clock algorithm
    private int evict(int ppn){
	    int offset;
	    if(VMKernel.diskPagesAvailable.size() != 0){
			offset = VMKernel.diskPagesAvailable.remove().intValue();
//			offset = nextAvail*pageSize;
//			//System.out.println("nextAvail: "+ nextAvail);
	    }
	    else{
		    offset = VMKernel.swapFile.length();
			////System.out.println("writing to disk at end");
	    }
    	    //System.out.println("writing to disk at "+ offset);

	    byte[] memory = Machine.processor().getMemory();

	    byte[] data = new byte [pageSize];

	    System.arraycopy(memory, ppn*pageSize, data, 0, pageSize);
	    
	    int bytesReturned = VMKernel.swapFile.write(offset,data,0,pageSize);

	    byte[] data2 = loadFromDisk(offset);

		
      return offset;
    }

    //Use to get a page back from swap
    private byte[] loadFromDisk(int offset){
		//System.out.println("retrieving from disk @ "+offset);
	    byte [] buff = new byte [pageSize];

	    int bytesReturned = VMKernel.swapFile.read(offset,buff,0,pageSize);

	    if(bytesReturned == -1){
		//System.out.println("Failed swap-page read");
		      return null;
	    }	
	
	    return buff;
    }

    //Use to put a page back into physical Memory
    private void storeIntoPMem(byte [] data, int location){
	    byte[] memory = Machine.processor().getMemory();
				
	    System.arraycopy(data, 0, memory, location*pageSize, pageSize);
    }




    /**
     * Handle a user exception. Called by
     * <tt>UserKernel.exceptionHandler()</tt>. The
     * <i>cause</i> argument identifies which exception occurred; see the
     * <tt>Processor.exceptionZZZ</tt> constants.
     *
     * @param	cause	the user exception that occurred.
     */
    public void handleException(int cause) {
	    Processor processor = Machine.processor();

	    switch (cause) {

	    case 2: // TLB Miss
		    handleTLBMiss();
        break;

	    default:
	        super.handleException(cause);
	        break;
	    }
    }

	private void printOutMem(int ppage){
		/*//System.out.println("PRINTING PMEM AT page: "+ppage);
		for(int i=0;i<pageSize;i++)
			System.out.print(Machine.processor().getMemory()[(ppage*pageSize)+i]+",");
		//System.out.println("");*/
	}

/*
    public CoffSection getCoff(int sectionNumb){

	return coff.getSection(sectionNumb);
    }

    public TranslationEntry getTE(int vpn)i{
	    return pageTable[vpn];
    }

    public NewTranslation getTE2(int vpn){

	return pageTable2[vpn];
    }
*/

    private void syncPageTabletoTLB(){

	for(int i = 0; i<Machine.processor().getTLBSize(); i++){
            TranslationEntry t =  Machine.processor().readTLBEntry(i);
            if(t.valid)
		Machine.processor().writeTLBEntry(i,pageTable[t.vpn]);
	}
    }

    protected NewTranslation[] pageTable2;
    //private static final int pageSize = Processor.pageSize;
    private static final char dbgProcess = 'a';
    private static final char dbgVM = 'v';
    private String[] args;
    public Lock IPTLock;
    public Lock pinnedLock;
	public Lock TLBLock;
	public Lock clockLock;
	public Lock memLock;
    public Condition allPinned;
}
